import java.util.ArrayList;


public class MergeSort {
	
	private ArrayList<String> tempArray = new ArrayList<String>();
	
	public MergeSort(String s){
		for (int i = 0;i < s.length();i++){
			tempArray.add(0,s.substring(i,i+1));
		}
	}
	
	public ArrayList<String> getTempArray() {
		return tempArray;
	}

	public ArrayList<String> mergeSort(ArrayList<String> tempArray){
		
		if (tempArray.size() == 1 ) return tempArray;
		
		int middlePointer = tempArray.size() /2;
		
		ArrayList<String> left =  fillSide(tempArray,middlePointer,true);
		ArrayList<String> right =  fillSide(tempArray,middlePointer,false);
		
		left = mergeSort(left);
		right = mergeSort(right);
		ArrayList<String> result = merge(left,right);
		return result;
		
	}
	
	private ArrayList<String> fillSide(ArrayList<String> temp,int midPointer,boolean isLeft){
		ArrayList<String> appSide = new ArrayList<String>();
		//This effectivly adds whats after or before the mid point depending on isLeft
		if (isLeft == true) for (int i = 0 ;i < midPointer;i++) appSide.add(temp.get(i));
			
		if (isLeft == false) for (int i = midPointer; i < temp.size();i++) appSide.add(temp.get(i));
		

			
		return appSide;
		
	}
	
	private ArrayList<String> merge(ArrayList<String> left,ArrayList<String> right){
		ArrayList<String> sortedArray = new ArrayList<String>();
		//Need to use false for the fillSide because the one where isLeft == true only works for the recursive step above :P
		//When its false, it uses the pointer as the start value which is what i need in both cases here
		while (left.isEmpty() == false || right.isEmpty() == false){
			
			if (right.isEmpty() == false && left.isEmpty() == false){
				String currentLeft = left.get(0);
				String currentRight = right.get(0);
				if (currentLeft.compareTo(currentRight) < 0) {
					sortedArray.add(currentLeft);
					left = fillSide(left,1,false);
				}
				else if (currentRight.compareTo(currentLeft) < 0) {
					sortedArray.add(currentRight);
					right = fillSide(right,1,false);
				}
				
				else {
					sortedArray.add(currentLeft);
					left = fillSide(left,1,false);
				}
				
			}
			
			if (left.isEmpty() == true){
				sortedArray.add(right.get(0));
				right = fillSide(right,1,false);
			}
			else if (right.isEmpty() == true){
				sortedArray.add(left.get(0));
				left = fillSide(left,1,false);
			}
			
		}
		
		
		return sortedArray;
		
	}
}
